# __main__
n = 5
g = [(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (2, 4), (3, 4)]

m = 2           # 假设只需要2种颜色即可完成着色
done = False    # 标记m种颜色能否完成图的着色
color = [0] * n # 记录每个顶点的颜色。0表示未涂色。

while not done:
    k = 0 # 从顶点0开始

    # 重新初始化颜色数组
    color[:] = [0 for _ in range(n)]

    while k >= 0:
        color[k] += 1   # 选择下一种颜色

        # 尝试使用小于等于m种颜色进行着色
        while color[k] <= m:
            # 以下if的判断条件与Java版本的isOk相同
            if all(color[i] != color[j] for i, j in g if i == k or j == k):
                break
            else: 
                color[k] += 1

        if color[k] > m: # 尝试了m种颜色仍存在冲突
            # 取消当前顶点着色，回溯到上一节点
            color[k] = 0 
            k -= 1
        else:
            if k < n - 1: # 未完成全部顶点着色,继续选择下一节点
                k = k + 1
            else:        # 已完成全部顶点着色，即k=n-1
                done = True # 已找到可行解, 完成
                break
    if not done: m += 1 # 没有找到m种颜色的可行解，令m自增，重新搜索

print('顶点颜色:', *color)
print('共需要颜色:', m)
